package leetcode_900;

import java.util.PriorityQueue;

/**
 *@author 周杨
 *FindAndReplaceInString_833 给定一个字符串 要求同时替换里面若干位置的字符子串 
 *describe:用优先队列排序 然后StringBuilder里插入字符 
 *2018年10月31日 上午10:44:46
 */
public class FindAndReplaceInString_833 {
	class Help{
		int index;
		String source;
		String target;
		public Help(int index,String source,String target) {
			this.index=index;
			this.source=source;
			this.target=target;
		}
	}
	
	public static void main(String[] args) {
		FindAndReplaceInString_833 test=new FindAndReplaceInString_833();
		//System.out.println(test.findReplaceString("abcd", new int[] {0,2}, new String[] {"ab","ec"}, new String[] {"eee","ffff"}));
		//System.out.println(test.findReplaceString("abcd", new int[] {0,2}, new String[] {"a","cd"}, new String[] {"eee","ffff"}));
		System.out.println(test.findReplaceString("vmokgggqzp", new int[] {3,5,1}, 
				new String[] {"kg","ggq","mo"}, new String[] {"s","so","bfr"}));
	}
	
	public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        PriorityQueue<Help> queue=new PriorityQueue<Help>((o1,o2)->o1.index-o2.index);//给插入区间排序
        char []chars=S.toCharArray();
        for(int i=0;i<indexes.length;++i) {
        	char []now=sources[i].toCharArray();
        	if(indexes[i]<chars.length) {//保证有此区间
        		int j=0;
        		while(j<now.length) {
        			if(now[j]!=chars[j+indexes[i]])
        				break;
        			++j;
        		}
        		if(j==now.length)
        			queue.offer(new Help(indexes[i],sources[i],targets[i]));//合法
        	}
        }
        StringBuilder sb=new StringBuilder(S);//重置这个字符串
        int offset=0;//偏移量
        while(!queue.isEmpty()) {
        	Help help=queue.poll();
        	sb.replace(help.index+offset, help.index+offset+help.source.length(), help.target);
        	offset+=help.target.length()-help.source.length();
        }
		return sb.toString();
    }
}
